﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GameLibrary.AI.EA
{
    using GameLibrary.Settlement;
    using GameLibrary.Player;
    using GameLibrary.Unit;
    using GameLibrary.Map;

    /// <summary>
    /// Find the best possible fight plan within a city's limit 
    /// </summary>
    [Serializable]
    public class TacticPlanner
    {
        #region inner class
        /// <summary>
        /// Represent instructions in assembly language
        /// </summary>
        public class Instruction
        {
            public UnitInfo Unit;
            public UnitActionFlags Action;
            public Position TargetPosition;

            public Instruction(UnitInfo unit, UnitActionFlags action, Position targetPos)
            {
                this.Unit = unit;
                this.Action = action;
                this.TargetPosition = targetPos;
            }
            public Instruction(Instruction inst)
            {
                this.Unit = inst.Unit;
                this.Action = inst.Action;
                this.TargetPosition = inst.TargetPosition;
            }
        }

        /// <summary>
        /// Represent an individual in population.
        /// </summary>
        public class Individual
        {
            /// <summary>
            /// Unit action list.
            /// </summary>
            public List<Instruction> Instructions = new List<Instruction>();
            public double Fitness = 0;

            public Dictionary<uint, UnitInfo> EffectedUnits;
            public Dictionary<uint, SettlementInfo> EffectedSettlements;
            public HashSet<uint> DiedUnits;

            public Individual()
            {
            }
            public Individual(Individual n)
            {
                this.Fitness = n.Fitness;
                n.Instructions.ForEach(inst => this.Instructions.Add(new Instruction(inst)));
            }
        }
        #endregion
        #region variables
        private bool NeedFightBack = false; // see if need to fight back
        private double[,] MoveCostMap;
        private int MaxProgramLength = 0;
        private int SegmentDisplacement = 10;
        /// <summary>
        /// usd in one segment crossover in deceidine whether insert or delete a segment of instructions.
        /// </summary>
        private double ProbOfInsert = 0.5;
        private int MinProgramLength = 1;
        /// <summary>
        /// Size of total population
        /// </summary>
        private int PopulationSize = 100;
        /// <summary>
        /// Size of additional population generated each turn.
        /// </summary>
        private int OffspringSize = 500;
        /// <summary>
        /// Population size of an island in island mode.
        /// </summary>
        private int IslandNumber = 10;
        private int PopulationPerIsland = 10;
        private int OffspringPerIsland = 50;
        private int InitInstrumentsNumber = 5;

        private List<List<Individual>> Population;
        private uint TotalTurns = 100;

        private uint PlayerID;
        private IEnumerable<RegionInfo> MemorizedMap; // map stored in PlayerMap

        private IEnumerable<RegionInfo> RealMap; // map in GameMap

        private MapObjects UnitList; // unit list of all sides
        private MapObjects SettlementList; // settlement list for all sides
  
        public delegate Tile.TileType _GetTileType(Position pos);
        public _GetTileType GetTileType;

        private Position NorthLeftCornerOfMap;

        /// <summary>
        /// Get unitlist from a map.
        /// </summary>
        /// <param name="map"></param>
        /// <returns></returns>
        private MapObjects GetUnitList(IEnumerable<RegionInfo> map)
        {
            MapObjects list = new MapObjects();
            foreach (var r in map)
            {
                foreach (UnitInfo u in r.GetUnits())
                {
                    list.Add(u);
                }
            }
            return list;
        }

        private MapObjects GetSettlementList(IEnumerable<RegionInfo> map)
        {
            MapObjects list = new MapObjects();
            foreach (var r in map)
            {
                foreach (SettlementInfo c in r.GetSettlements())
                {
                    list.Add(c);
                }
            }
            return list;
        }

        #endregion

        #region constructor

        /// <summary>
        /// 
        /// </summary>
        /// <param name="threatMap">A map shows threat level.</param>
        /// <param name="memorizedMap">All infomation about the map.</param>
        /// <param name="populationSize">Size of total population.</param>
        /// <param name="offspringSize">Size of additional population which will be truncated in select stage.</param>
        /// <param name="microMutateRate_selectUnitOrAction">Ratio about whether select two unit to swap or change one unit's action.</param>
        /// <param name="islandNumber">Island mode. How many population on a island or deme.</param>
        public TacticPlanner(
            uint ownerID, 
            _GetTileType getTileType,
            IEnumerable<RegionInfo> realMap,
            IEnumerable<RegionInfo> memorizedMap,
            double[,] costmap, // move cost map centered on started region
            bool needFightBack,
            uint totalTurns = 10,
            int populationSize = 100, // population size
            int offspringSize = 500, // extra population will be removed during select action
            int islandNumber = 10,
            int segmentDisplacement = 10, 
            int initInstNumber = 5, 
            double Pins = 0.5, 
            int minProgLength = 1
            )
        {
            this.GetTileType = getTileType;
            this.MoveCostMap = costmap;
            this.NeedFightBack = needFightBack;
            this.PlayerID = ownerID;
            this.MemorizedMap = memorizedMap;
            this.TotalTurns = totalTurns;
            this.PopulationSize = populationSize;
            this.IslandNumber = islandNumber;
            this.OffspringSize = offspringSize;
            this.Population = new List<List<Individual>>();
            int islandPopulation = (this.OffspringSize + this.PopulationSize) / this.IslandNumber;
            this.PopulationPerIsland = this.PopulationSize / this.IslandNumber;
            this.OffspringPerIsland = this.OffspringSize / this.IslandNumber;
            this.InitInstrumentsNumber = initInstNumber;
            this.UnitList = GetUnitList(this.MemorizedMap);
            this.SettlementList = GetSettlementList(this.MemorizedMap);
            double TotalAP = 0;
            foreach (UnitInfo u in this.UnitList.GetObjsByOwnerID(this.PlayerID))
            {
                TotalAP += u.Current.AP;
            }
            this.MaxProgramLength = ((int)TotalAP) * 3;
            this.MinProgramLength = minProgLength;
            this.ProbOfInsert = Pins;

            var xlist = (from r in this.MemorizedMap
                         select r.Start.X).ToList();
            var ylist = (from r in this.MemorizedMap
                         select r.Start.Y).ToList();
            this.NorthLeftCornerOfMap = new Position(
                xlist.Min(), ylist.Min());

            this.RealMap = realMap;
        }

        #endregion

        #region valid

        private void GetValidIndividual(ref Individual individual)
        {
            for (int i = 0; i < this.InitInstrumentsNumber; i++)
            {
                int pos = GMHelper.Rand.Next(this.UnitList.GetObjsCountOfAOwnerID(this.PlayerID));
                Instruction inst = GetValidInstruction(                   
                    this.UnitList.GetObjsByOwnerID(this.PlayerID).ElementAt(pos) as UnitInfo);
                
                individual.Instructions.Add(inst);
            }
        }

        private UnitActionFlags GetRandomActionFlag()
        {
            return UnitHelper.GetNormalActionFlag(
                        GMHelper.Rand.Next(UnitHelper.NormalActionFlagCount)
                );
        }

        private Position GetRandomPosition()
        {
            return new Position(
                GMHelper.Rand.Next(this.MoveCostMap.GetLength(0)),
                GMHelper.Rand.Next(this.MoveCostMap.GetLength(1))
                ) + this.NorthLeftCornerOfMap;
        }
        private Instruction GetValidInstruction(UnitInfo unit)
        {
            UnitActionFlags flag = this.GetRandomActionFlag();

            Position position = this.GetRandomPosition();

            Instruction inst = new Instruction(unit, flag, position);

            return inst;
        }

        #endregion

        #region init

        private void Init()
        {
            for (int island = 0; island < IslandNumber; island++) // for each island
            {
                this.Population.Add(new List<Individual>());

                for (int populationCount = 0; 
                    populationCount < PopulationPerIsland; 
                    populationCount++) // create population
                {
                    Individual individual = new Individual();
                    this.GetValidIndividual(ref individual);
                    this.Population[island].Add(individual);
                }
                this.Population[island].ForEach(n => FindFitness(n)); // find each individual's fitness
            } 
        }

        #endregion

        #region select

        /// <summary>
        /// Select two node as parent for reproduction.
        /// double tournament selection
        /// </summary>
        /// <param name="A">parent a</param>
        /// <param name="B">parent b</param>
        /// <param name="list"> candidate list </param>
        private void DoubleTournamentSelection(
            out Individual A, 
            out Individual B, 
            List<Individual> list)
        {
            List<Individual> candidates = new List<Individual>();
            int firstRoundSize = 6;
            for (int i = 0; i < firstRoundSize; i++)
            {
                int pos = GMHelper.Rand.Next(list.Count);
                candidates.Add(list[pos]);
            }
            List<Individual> secondRound = new List<Individual>();
            for (int i = 0; i < firstRoundSize; i+=2)
            {
                if (candidates[i].Fitness >= candidates[i + 1].Fitness)
                    secondRound.Add(candidates[i]);
                else
                    secondRound.Add(candidates[i + 1]);
            }
            secondRound.Sort(new NodeComparer());
            A = secondRound[0];
            B = secondRound[1];
        }

        #endregion

        #region crossover

        /// <summary>
        /// One segment crossover.
        /// </summary>
        /// <param name="instructionList1"></param>
        /// <param name="instructionList2"></param>
        /// <param name="A"></param>
        private List<Instruction> Crossover(
            List<Instruction> instructionList1, 
            List<Instruction> instructionList2)
        {
            List<Instruction> list = new List<Instruction>();
            instructionList1.ForEach(n => list.Add(new Instruction(n)));
            if (
                (
                    GMHelper.Rand.NextDouble() > ProbOfInsert 
                 && instructionList1.Count <= this.MaxProgramLength
                ) 
                || instructionList1.Count <= this.MinProgramLength)
                AddSegment(instructionList1, instructionList2, ref list);
            else
                DelSegment(ref list);
            return list;
        }

        /// <summary>
        /// Add a segment from list2 to output
        /// </summary>
        /// <param name="instructionList1">same content as output</param>
        /// <param name="instructionList2">list containing segment need to be transfered</param>
        /// <param name="output"></param>
        private void AddSegment(
            List<Instruction> instructionList1, 
            List<Instruction> instructionList2, 
            ref List<Instruction> output)
        {
            int pos1 = GMHelper.Rand.Next(instructionList1.Count);
            int min = -1 * this.SegmentDisplacement + pos1; // lower limit
            int max = this.SegmentDisplacement + pos1; // upper limit
            if (min < 0) min = 0; // reset lower limit if less than 0
            if (max > instructionList2.Count) max = instructionList2.Count; // reset upper limit
            if (min > max)
            {
                var swp = max;
                max = min;
                min = swp;
            }
            if (min > instructionList2.Count)
                min = instructionList2.Count;
            if (max > instructionList2.Count)
                max = instructionList2.Count;                     
            int pos2 = GMHelper.Rand.Next(min, max);

            int length = instructionList2.Count - pos2;
            
            length = GMHelper.Rand.Next(length);
            if (length > instructionList2.Count - pos2)
                length = instructionList2.Count;
            List<Instruction> tmp = new List<Instruction>();
            instructionList2.GetRange(pos2, length).ForEach(n => tmp.Add(new Instruction(n)));
            output.InsertRange(pos1, tmp);
        }

        /// <summary>
        /// Delete one instruction from list.
        /// </summary>
        /// <param name="instructionList"></param>
        private void DelSegment(ref List<Instruction> instructionList)
        {
            int pos = GMHelper.Rand.Next(instructionList.Count);
            instructionList.RemoveAt(pos);
        }

        #endregion

        #region mutate

        /// <summary>
        /// Mutate one instruction
        /// </summary>
        /// <param name="instructionList"></param>
        /// <returns></returns>
        private void Mutate(ref List<Instruction> instructionList)
        {
            int pos = GMHelper.Rand.Next(instructionList.Count);
            Instruction inst = instructionList[pos];
            MutateInstruction(ref inst);
        }

        private void MutateInstruction(ref Instruction inst)
        {
            int select = GMHelper.Rand.Next(3); // select one of three segment of instruction
            switch (select)
            {
                case 0: // unit
                    ChangeUnit(ref inst);
                    break;
                case 1: // action
                    ChangeAction(ref inst);
                    break;
                case 2: // position
                    ChangePosition(ref inst);
                    break;
                default:
                    throw new Exceptions.ShouldNotReachException(" ");
            }
        }

        private void ChangeUnit(ref Instruction inst)
        {
            int pos = GMHelper.Rand.Next(
                    this.UnitList.GetObjsCountOfAOwnerID(this.PlayerID)
                    );
            UnitInfo info = 
                this.UnitList.GetObjsByOwnerID(this.PlayerID).ElementAt(pos) 
                as UnitInfo;
            inst.Unit = info;
        }

        private void ChangeAction(ref Instruction inst)
        {
            UnitActionFlags flag = this.GetRandomActionFlag();

            inst.Action = flag;
        }

        private void ChangePosition(ref Instruction inst)
        {
            Position pos = this.GetRandomPosition();
            inst.TargetPosition = pos;
        }

        #endregion

        #region find fitness

        #region interpert program
        #region program
  
        private void GetProgramResult(
            List<Instruction> instructionList,
            MapObjects unitList,
            MapObjects settlementList,
            out Dictionary<uint,UnitInfo> EffectedUnits,
            out Dictionary<uint,SettlementInfo> EffectedSettlements,
            out HashSet<uint> DiedUnits
            )
        {

            Dictionary<uint, double> APList = new Dictionary<uint, double>();
            foreach (UnitInfo unit in unitList.GetObjsByOwnerID(this.PlayerID))
            {
                APList.Add(unit.ID, unit.Current.AP);
            }

            EffectedUnits = new Dictionary<uint,UnitInfo>();
            EffectedSettlements = new Dictionary<uint,SettlementInfo>();

            DiedUnits = new HashSet<uint>();
            double total = APList.Values.Sum();

            for (int i = 0; i < instructionList.Count; i++)
            {
                if (total <= 0) // no one can move
                    break;
                if (APList[instructionList[i].Unit.ID] <= 0) // unit i can not move
                    continue;
                else
                {
                    if (
                        instructionList[i].Unit.Template.Actions.HasFlag(instructionList[i].Action) == false // cannot perform action
                        || DiedUnits.Contains(instructionList[i].Unit.ID) == true // already died
                        || APList[instructionList[i].Unit.ID] <= 0 // do not have ap
                        )
                        continue; //intron
                    else
                    {
                        UnitInfo unit;
                        if (EffectedUnits.ContainsKey(instructionList[i].Unit.ID) == false)
                        {
                            unit = new UnitInfo(instructionList[i].Unit);
                            EffectedUnits.Add(unit.ID, unit);
                        }
                        else
                            unit = EffectedUnits[instructionList[i].Unit.ID];

                        switch (instructionList[i].Action)
                        {
                            case UnitActionFlags.Move:
                                float tmp = this.MoveUnit(
                                    unit,
                                    instructionList[i].TargetPosition,
                                    unitList,
                                    settlementList,
                                    ref EffectedUnits,
                                    ref EffectedSettlements,
                                    ref DiedUnits
                                    );
                                if (tmp != float.NaN) // not intron
                                {
                                    APList[unit.ID] -= tmp;
                                    total -= tmp;
                                }
                                break;
                            case UnitActionFlags.Fortify:
                                this.FortifyUnit(
                                    unit
                                     );
                                total -= APList[unit.ID];
                                APList[unit.ID] = 0;
                                break;
                            case UnitActionFlags.Attack:
                                if (
                                    this.Attack(
                                            unit,
                                            instructionList[i].TargetPosition,
                                            unitList,
                                            settlementList,
                                            ref EffectedUnits,
                                            ref EffectedSettlements,
                                            ref DiedUnits
                                        ) == true
                                    )
                                {
                                    APList[unit.ID] -= 1;
                                    total -= 1;
                                }
                                break;
                            default:
                                throw new Exceptions.ShouldNotReachException("");
                        }
                    }
                }
            }
        }

        #endregion

        #region move unit

        /// <summary>
        /// Move unit accross the map. Change map information.
        /// Try to move to that position, until spend all ap of that unit.
        /// Return used ap.
        /// </summary>
        /// <param name="unitInfo"></param>
        /// <param name="current"></param>
        /// <param name="to"></param>
        /// <param name="map"></param>
        private float MoveUnit(
            UnitInfo unitInfo, 
            Position to, 
            MapObjects unitList,
            MapObjects settlementList,
            ref Dictionary<uint,UnitInfo> effectedUnits,
            ref Dictionary<uint,SettlementInfo> effectedCities,
            ref HashSet<uint> diedUnits
            )
        {
            if (unitInfo.Location == to) // no path between same position
                return float.NaN;

            Position frompos = new Position(unitInfo.Location.X % GMHelper.RegionWidth,
                                        unitInfo.Location.Y % GMHelper.RegionHeight);
            Position toPos = new Position(to.X % GMHelper.RegionWidth,
                                            to.Y % GMHelper.RegionHeight);

            List<Position> path = new AI.ShortestPath.AStar(
                        this.MoveCostMap, frompos, toPos).GetResult();
            UnitInfo unit;
            if (effectedUnits.ContainsKey(unitInfo.ID) == false)
            {
                unit = new UnitInfo(unitInfo);
                effectedUnits.Add(unit.ID, unit);
            }
            else
                unit = effectedUnits[unitInfo.ID];

            float unitAP = unit.Current.AP;

            HashSet <uint> DiedUnits = diedUnits;
            Dictionary<uint, SettlementInfo> EffectedCities = effectedCities;

            foreach(Position p in path) // check if path is a valid path
                if (MoveCostMap[p.X, p.Y] == double.NaN) // cannot move through 
                    return float.NaN; // intron

            Position lastPosition = unit.Location;
            foreach(Position position in path) // this path is based on moveCostMap start from 0,0
            {
                unitAP -= (float) MoveCostMap[position.X, position.Y];

                if (unitAP <= 0) // check whether this unit can move along the path
                {
                    unitAP += (float)MoveCostMap[position.X, position.Y]; // reverse
                    break;
                }
                else
                    lastPosition = position;

                //check whether have opponent unit on tile p

                var unitsOnPosition = unitList.GetObjsByPosition(position 
                                                               + this.NorthLeftCornerOfMap);
                
                IEnumerable<UnitInfo> opponentUnits;
                if (unitsOnPosition != null)
                    opponentUnits = from u in unitsOnPosition
                                    where u.OwnerID != this.PlayerID
                                       && DiedUnits.Contains(u.ID) == false
                                    select u as UnitInfo;
                else
                    opponentUnits = new List<UnitInfo>();

                if (opponentUnits.Count() > 0)
                {                    
                    this.Attack(
                        unit,
                        position + this.NorthLeftCornerOfMap,
                        unitList,
                        settlementList,
                        ref effectedUnits,
                        ref effectedCities,
                        ref diedUnits);

                   var currentUnitsOnPosition = from u in unitList.GetObjsByPosition(position)
                                                where DiedUnits.Contains(u.ID) == false
                                                   && u.OwnerID != this.PlayerID
                                                select u as UnitInfo;

                    if (diedUnits.Contains(unit.ID) == true // lost 
                        || currentUnitsOnPosition.Count() > 0 // more than 1 unit, which need to fight twice or more
                        )
                    {

                        lastPosition = this.GetPositionBeforeCurrentPosition(path, position); // retreat to previous position
                     
                        unitAP--;
                        break; // stop here
                    }
                    else // occupy and stop
                    {
                        this.OccupyCity(
                            position,
                            settlementList,
                            ref effectedCities);

                        unitAP--;
                        break; // stop here
                    }
                }
                else // occupy and move on
                {
                    this.OccupyCity(
                        position, 
                        settlementList,
                        ref effectedCities);
                    unitAP--;
                }
                
            }
            if (unitAP < 0)
                unitAP = 0;         

            unitAP = unit.Current.AP - unitAP;
            unit.Current.AP = unit.Current.AP - unitAP ;
            unit.SetLocation(lastPosition);
            return unitAP;
        }
        private Position GetPositionBeforeCurrentPosition(List<Position> path, Position currentPosition)
        {
            int index = path.IndexOf(currentPosition);
            if (index == 0)
                return currentPosition;
            else
                return path.ElementAt(index - 1);
        }
        /// <summary>
        /// return false if no opponent city.
        /// Else return true
        /// </summary>
        /// <param name="effectedCities"></param>
        /// <returns></returns> 
        private bool OccupyCity(
            Position position, 
            MapObjects settlementList,
            ref Dictionary<uint, 
            SettlementInfo> effectedCities)
        {
            Dictionary<uint, SettlementInfo> EffectedCities = effectedCities;
            // do not have opponent unit
            //check whether have opponent city on tile p

            var opponentSettlements = from c in settlementList.Values
                               where c.OwnerID != this.PlayerID
                               && EffectedCities.ContainsKey(c.ID) == false
                               && c.Location == (position + this.NorthLeftCornerOfMap)
                               select c;

            if (opponentSettlements.Count() > 1) // error condition
            {
                throw new Exceptions.ShouldNotReachException("one city per tile breaks.");
            }
            else
                if (opponentSettlements.Count() <= 0) // no opponent city
                    return false;
                else // one opponent city acquired
                {
                    SettlementInfo cinfo = 
                        new SettlementInfo(opponentSettlements.First() as SettlementInfo);
                    cinfo.SetOwnerID(this.PlayerID);
                    effectedCities.Add(cinfo.ID, cinfo);
                    return true;
                }
        }

        #endregion

        #region fortify

        private void FortifyUnit(UnitInfo info)
        {

            info.Current.Defence =
                (uint)(info.Current.Defence
                        * this.GetTileType(info.Location).DefenceEffect
                        * info.Current.AP);
            info.Current.AP = 0;
        }

        #endregion

        #region Attack

        /// <summary>
        /// Return true if target within range and is a valid target.
        /// Otherwise return false.
        /// </summary>
        /// <param name="info"></param>
        /// <param name="target"></param>
        /// <param name="map"></param>
        /// <returns></returns>
        private bool Attack(
            UnitInfo info, 
            Position target, 
            MapObjects unitList,
            MapObjects settlementList,
            ref Dictionary<uint,UnitInfo> effectedUnits,
            ref Dictionary<uint,SettlementInfo> effectedCities,
            ref HashSet<uint> diedUnits
            )
        {
            if (info.Location == target)
                return false;

            uint ownerID;
            var objsAtPosition = settlementList.GetObjsByPosition(target);

            if (objsAtPosition != null)
                ownerID = objsAtPosition.First().OwnerID;
            else
            {
                objsAtPosition = unitList.GetObjsByPosition(target);
                if (objsAtPosition != null)
                    ownerID = objsAtPosition.First().OwnerID;
                else
                    ownerID = 0;
            }
            
            HashSet<uint> DiedUnits = diedUnits;
            var EffectedUnits = effectedUnits;

            if (
                info.Location.FindDistance(target) > info.Template.AttackRange // out of range
                || ownerID == this.PlayerID // owned by self
                || ownerID == 0)// owned by nature
                return false; // intron
            else
            {
                // attack opponent's units first
                var objs = unitList.GetObjsByPosition(target);
                if (objs != null)
                {
                    // must alive
                    // not already died
                    var notDied = from o in objs
                                where DiedUnits.Contains(o.ID) == false
                                select o;
                    if (notDied.Count() == 0)
                        return false; // intron;

                    // this too, try to make sure all unit in ulist is alive
                    var haveRemainingHp = from o in notDied
                                          where (EffectedUnits.ContainsKey(o.ID) 
                                               ? EffectedUnits[o.ID].Current.HP > 0 
                                               : true
                                               )
                                          select o;
                    if (haveRemainingHp.Count() == 0)
                        return false;

                    UnitInfo u;
                    if (effectedUnits.ContainsKey(haveRemainingHp.First().ID) == true)
                        u = effectedUnits[haveRemainingHp.First().ID];
                    else
                    {
                        u = new UnitInfo(haveRemainingHp.First() as UnitInfo);
                        effectedUnits.Add(u.ID, u);
                    }
                    float attHp, defHP;
                    AI.FightSimulator.GetResult(info, u, out attHp, out defHP);

                    if (attHp <= 0)
                    {
                        diedUnits.Add(info.ID);
                        info.Current.HP = 0;
                    }
                    else
                    {
                        info.Current.HP = attHp;
                        info.Current.AP = info.Current.AP - 1;
                    }

                    if (defHP <= 0)
                    {
                        diedUnits.Add(u.ID);
                        u.Current.HP = 0;
                    }
                    else
                        u.Current.HP = defHP;
                    return true;
                }
                return false;
            }
        }
        #endregion

        #endregion

        #region get total remaining ap

        private double GetTotalRemainingAP(Dictionary<uint, double> list)
        {
            double total = 0;
                total = list.Sum(n=>n.Value);
            return total;
        }

        #endregion

        private void FindFitness(
            Individual individual,
            MapObjects unitList = null,
            MapObjects settlementList = null
            )
        {
            Dictionary<uint, UnitInfo> effectedUnits;
            Dictionary<uint, SettlementInfo> effectedCities;
            HashSet<uint> diedUnits;

            if (unitList == null)
                unitList = this.UnitList;

            if (settlementList == null)
                settlementList = this.SettlementList;

            this.GetProgramResult(
                individual.Instructions,
                unitList,
                settlementList,
                out effectedUnits,
                out effectedCities,
                out diedUnits);

            individual.EffectedSettlements = effectedCities;
            individual.EffectedUnits = effectedUnits;
            individual.DiedUnits = diedUnits;

            List<uint> keys = new List<uint>(unitList.GetOwnerIDs());

            //currently only two player
            keys.Remove(this.PlayerID); // remove self
            keys.Remove(0); // remove nature
            if (this.NeedFightBack == true && keys.Count > 0)
            {
                HashSet<RegionInfo> map = new HashSet<RegionInfo>();
                foreach (var r in this.MemorizedMap)
                {
                    RegionInfo reg = new RegionInfo(r);
                    var units = from u in effectedUnits.Values
                                where MapHelper.FindRegion(u.Location) == reg.Start
                                && individual.DiedUnits.Contains(u.ID) == false
                                select u;
                    foreach (var u in units)
                    {
                        reg.RemoveUnit(u.ID);
                        reg.AddUnit(u);
                    }
                    var cities = from c in effectedCities.Values
                                 where MapHelper.FindRegion(c.Location) == reg.Start
                                 select c;
                    foreach (var c in cities)
                    {
                        reg.RemoveSettlement(c.ID);
                        reg.AddSettlement(c);
                    }
                }                

                Individual fightBackResult =  new TacticPlanner(
                    keys[0],
                    this.GetTileType,
                    this.RealMap,
                    this.MemorizedMap,
                    this.MoveCostMap,
                    false,
                    populationSize: 10,
                    offspringSize:10
                    ).GetResult(); // should change to foreach poltic hostile opponent.

                individual.Fitness -= fightBackResult.Fitness;
            }
            GetFitness(individual);
        }
        /// <summary>
        /// Get gain/loss score through calculate differences between original map and result map.
        /// positive/negative --
        ///     same with ownerID -- positive
        ///     other             -- negative // only two player considered
        /// worth
        ///     city -- total production
        ///     village -- production worth in city if owned by any city or only its production
        ///     unit -- production worth
        /// </summary>
        /// <param name="map"></param>
        /// <returns></returns>
        private void GetFitness(Individual n)
        {            
            foreach (UnitInfo u in n.EffectedUnits.Values)
            {
                if (n.DiedUnits.Contains(u.ID) == true) // died units
                    if (u.OwnerID == this.PlayerID)
                        n.Fitness -= u.GetTotalCost(); // player loss
                    else
                        n.Fitness += u.GetTotalCost(); // opponent loss
             //   else // units change statues
             //   {
             //       var original = this.UnitList[u.ID] as UnitInfo;
             //       float change = original.Current.HP - u.Current.HP;
                             //     + original.Current.AP - u.Current.AP
                             //     + original.Current.SP - u.Current.SP
                            //      + u.Current.Attack - original.Current.Attack
                            //      + u.Current.Defence - original.Current.Defence;
                  
             //       if (u.OwnerID != this.PlayerID)
             //           n.Fitness += change;
                  //  else
                  //      n.Fitness -= change;
             //   }
            }

            foreach (SettlementInfo c in n.EffectedSettlements.Values)
            {
                SettlementInfo original = this.SettlementList[c.ID] as SettlementInfo;
                n.Fitness += original.Production;
            }
        }
        #endregion

        #region next generation

        private void NextGeneration()
        {
            for (int i = 0; i < IslandNumber; i++) // for each deme
            {
                List<Individual> population = new List<Individual>();

                while (population.Count < OffspringPerIsland )//+ PopulationPerIsland))
                {
                    Individual A, B;
                    DoubleTournamentSelection(out A, out B, Population[i]);
                    var instList = Crossover(A.Instructions, B.Instructions);
                    Mutate(ref instList);
                    Individual n = new Individual();
                    n.Instructions = instList;
                    population.Add(n);
                }
                //population.ForEach(n => this.FindFitness(n)); // find fitness
                population.AsParallel().ForAll(n => this.FindFitness(n));
                population.AddRange(Population[i]);
                population.Add(this.Population[(i + 1) % this.IslandNumber].First()); // immigration
                population.Sort(new NodeComparer());
                population.RemoveRange(this.PopulationPerIsland, population.Count - this.PopulationPerIsland); // truncate selection
                this.Population[i] = population;                
            }
        }

        class NodeComparer : IComparer<Individual>
        {
            #region IComparer<Node> Members

            public int Compare(Individual x, Individual y)
            {
                return -x.Fitness.CompareTo(y.Fitness);
            }

            #endregion
        }

        #endregion

        #region Get result

        private Individual GetResult()
        {
            Init();
            for (int i = 0; i < this.TotalTurns; i++)
            {
                NextGeneration();
            }
            List<Individual> list = new List<Individual>();
            this.Population.ForEach(n => list.AddRange(n));
            list.Sort(new NodeComparer());

            var best = list.First();

            MapObjects unitList = this.GetUnitList(this.RealMap);
            MapObjects settlementList = this.GetSettlementList(this.RealMap);

            best.DiedUnits = null;
            best.EffectedSettlements = null;
            best.EffectedUnits = null;

            this.GetProgramResult(
                best.Instructions,
                unitList,
                settlementList,
                out best.EffectedUnits,
                out best.EffectedSettlements,
                out best.DiedUnits);               
            
            return best;
        }

        public void GetResult(
            out Dictionary<uint, UnitInfo> effectedUnits,
            out Dictionary<uint, SettlementInfo> effectedCities,
            out HashSet<uint> diedUnits)
        {            
            Individual n = this.GetResult();
            effectedCities = n.EffectedSettlements;
            effectedUnits = n.EffectedUnits;
            diedUnits = n.DiedUnits;
        }

        #endregion
    }
}
